package com.da.javatest.algorithm;

/**
 * @author chenlida
 * @date 2019/4/9 10:39
 * @description
 */
public class MaxHeap2 {
    private int[] a; // 数组，从下标1开始存储数据
    private int n; // 堆可以存储的最大数据个数
    private int count; // 堆中已经存储的数据个数

    public MaxHeap2(int capacity) {
        a = new int[capacity + 1];
        n = capacity;
        count = 0;
    }

    public void insert(int data) {
        if (count >= n) {
            return; // 堆满了
        }
        ++count;
        a[count] = data;
        int i = count;
        while (i / 2 > 0 && a[i] > a[i / 2]) { // 自下往上堆化
            swap(a, i, i / 2); // swap()函数作用：交换下标为i和i/2的两个元素
            i = i / 2;
        }
    }

    private static void swap(int[] data, int i, int j) {
        int temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }

    public void removeMax() {
        if (count == 0) {
            return; // 堆中没有数据
        }
        a[1] = a[count];
        --count;
        heapify(a, count, 1);
    }

    private void heapify(int[] a, int n, int i) { // 自上往下堆化
        while (true) {
            int maxPos = i;
            if (i * 2 <= n && a[i] < a[i * 2]) { maxPos = i * 2; }
            if (i * 2 + 1 <= n && a[maxPos] < a[i * 2 + 1]) { maxPos = i * 2 + 1; }
            if (maxPos == i) { break; }
            swap(a, i, maxPos);
            i = maxPos;
        }
    }

    private void buildHeap(int[] a, int n) {
        for (int i = n / 2; i >= 1; --i) {
            heapify(a, n, i);
        }
    }

    public void sort() {
        buildHeap(a, count);
        int k = count;
        while (k > 1) {
            swap(a, 1, k);
            --k;
            heapify(a, k, 1);
        }
    }

    public void print() {
        for (int i = 1; i <= count; i++) {
            System.out.print(a[i] + " ");
        }
    }

    public static void main(String[] args) {
        MaxHeap2 heap = new MaxHeap2(8);
        heap.insert(2);
        heap.insert(123);
        heap.insert(77);
        heap.insert(195);
        heap.insert(11);
        heap.insert(33);
        heap.insert(148);
        heap.insert(74);
        heap.print();
        heap.removeMax();
        System.out.println();
        heap.print();
        heap.sort();
        System.out.println();
        heap.print();
    }
}
